#include <yatak/kheap.h>
#include <yatak/mutex.h>
#include <string.h>
#include <map.h>

void swap_map(multi_map_t ** map, char * key1, char * key2)
{
	multi_map_t * pre1 = NULL;
	multi_map_t * pre2 = NULL;
	multi_map_t * map1 = NULL;
	multi_map_t * map2 = NULL;
	multi_map_t * tmp = *map;
	while (tmp->next)
	{
		if (!strcmp(tmp->key, key1))
			map1 = tmp;
		if (!strcmp(tmp->key, key2))
			map2 = tmp;
		if (!strcmp(tmp->next->key, key1))
			pre1 = tmp;
		if (!strcmp(tmp->next->key, key2))
			pre2 = tmp;
		if (map1 && map2)
			break;
	}
	if (!map1 || !map2)
		return;
	if (!pre1)
		pre1->next = map2;
	if (!pre2)
		pre2->next = map1;
	tmp = map1->next;
	map1->next = map2->next;
	map2->next = tmp;
} 

void QuickSort(multi_map_t ** map, int p, int r)
{
	int i,j, k;
	char x [256];
	char k1 [256];
	char k2 [256];
	multi_map_t * tmp;
	i=p;
	if (r == -1)
	{
		r = 0;
		tmp = *map;
		while (tmp->next)
		{
			tmp = tmp->next;
			r++;
		}
	}
	j=r;
	
	tmp = *map;
	k = i;
	while (k && tmp->next)
	{
		tmp = tmp->next;
		k--;
	}
	k = (i+j)/2;
	while (k && tmp->next)
	{
		tmp = tmp->next;
		k--;
	}
	strcpy (x,tmp->key);
	do
	{
		tmp = *map;
		k = i;
		while (k && tmp->next)
		{
			tmp = tmp->next;
			k--;
		}
		while(tmp && strcmp (tmp->key,x) == -1)
		{
			tmp = tmp->next;
			i++;
		}
		if (tmp)
			strcpy (k1,tmp->key);
		else
			k1 [0] = '\0';
		while(tmp && strcmp (tmp->key,x) == 1)
		{
			j--;
			k = j;
			tmp = map;
			while (k && tmp->next)
			{
				tmp = tmp->next;
				k--;
			}
		}
		
		if (tmp)
			strcpy (k2,tmp->key);
		else
			k2 [0] = '\0';
		if(i<=j)
		{
			swap_map(map,k1,k2);
			i++;
			j--;
		}
	}
	while(i<=j);
	if(j>p)
		QuickSort(map,p,j);
	if(i<r)
		QuickSort(map,i,r);
}

int add2multi_map (multi_map_t ** map, char * key, void * item, size_t size)
{
	if (!key)
		return 1;
	static mutex_t mutex;
	mutex_enter(&mutex);
	if (!(*map))
	{
		*map = ((multi_map_t *) kmalloc (sizeof (multi_map_t)));
		strcpy((*map)->key, key);
		(*map)->values = NULL;
		(*map)->values = add2List((*map)->values,item,size);
		(*map)->next = NULL;
	}
	else
	{
		multi_map_t * tmp = *map;
		while (tmp->next)
		{
			if (!strcmp(tmp->key,key))
				break;
			tmp = tmp->next;
		}
		
		if (!strcmp(tmp->key,key))
		{
			tmp->values = add2List(tmp->values,item,size);
		}
		else
		{
			tmp->next = (multi_map_t *) kmalloc (sizeof (multi_map_t));
			tmp = tmp->next;
			strcpy(tmp->key, key);
			tmp->values = NULL;
			tmp->values = add2List(tmp->values,item,size);
			tmp->next = NULL;
			QuickSort (map,0,0);
		}
	}
	mutex_leave(&mutex);
	return 0;
}

list_t * get_multi_map_items (multi_map_t * map, char * key)
{
	if (!(map) || !key)
		return NULL;
	static mutex_t mutex;
	mutex_enter(&mutex);
	multi_map_t * tmp = map;
	while (tmp->next)
	{
		if (!strcmp(tmp->key,key))
			break;
		tmp = tmp->next;
	}
	mutex_leave(&mutex);
	if (!strcmp(tmp->key,key))
		return tmp->values;
	return NULL;
}

int remove_multi_map_items (multi_map_t ** map, char * key)
{
	if (!(*map) || !key)
		return 1;
	static mutex_t mutex;
	mutex_enter(&mutex);
	multi_map_t * tmp = *map;
	while (tmp->next)
	{
		if (!strcmp(tmp->next->key,key))
		{
			tmp->next = tmp->next->next;
			tmp = tmp->next;
			break;
		}
		if (!strcmp(tmp->key,key))
			break;
		tmp = tmp->next;
	}
	mutex_leave(&mutex);
	if (!strcmp(tmp->key,key))
	{
		remove_list (tmp->values);
		if (tmp == *map)
			map = &((*map)->next);
		kfree (tmp);
		return 0;
	}
	return 1;
}

int remove_multi_map (multi_map_t ** map)
{
	if (!(*map))
		return 1;
	static mutex_t mutex;
	mutex_enter(&mutex);
	while (!remove_multi_map_items (map,(*map)->key));
	mutex_leave(&mutex);
	return 0;
}